#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Node:
    __slots__ = ['value', 'next']

    def __init__(self, value=None, next=None):
        self.value = value

        if next:
            self.next = next
        else:
            self.next = None

    def show_v(self):
        print('v: %s' % self.value)


class Solution:
    """
    @param head: the List
    @param k: rotate to the right k places
    @return: the list after rotation
    """
    def rotateRight(self, head, k):
        # write your code here
        # k 有可能大于链表长度
        if k == 0 or (not head):
            return head

        self.head = head
        k1, tail = self.reverse_k_and_tail(k+1)

        if not k1:
            return head

        k = self.next(k1)
        print(k)
        if head is k:
            # 刚好一个循环
            print('hit')
            return head

        tail.next = head
        k1.next = None
        return k

    def next(self, node):
        # loop list's next
        if not node.next:
            return self.head
        else:
            return node.next

    def kth(self, k):
        ''' 下标从1开始, 可能大于链表长度, 那就循环继续 '''
        head = self.head    # 这是第一个: k = 1
        probe = head
        if not head:
            return head

        k -= 1
        while k:
            k -= 1

            probe = self.next(probe)

        return probe

    def reverse_k_and_tail(self, k):
        ''' 倒数第k个元素, 下表从1 开始
            [1, 2, 3, 4, 5] 倒数第1个是5
            [1, 2, 3, 4, 5] 倒数第2个是4
        '''

        k_node = self.kth(k)
        if not k_node:
            return k_node, None

        n1, n2 = self.head, k_node
        while n2.next:
            n1, n2 = n1.next, n2.next

        return n1, n2

def build_link_list():
    l5 = Node(5, None)
    l4 = Node(4, l5)
    l3 = Node(3, l4)
    l2 = Node(2, l3)
    l1 = Node(1, l2)

    # l2 = Node(2, None)
    # l1 = Node(1, l2)

    # l1 = Node(1, None)

    return l1

def main():
    print("start main")
    l = build_link_list()
    s = Solution()
    s.rotateRight(l, 10)
    # s.rotateRight(l, 15)
    # n = s.kth()
    # n.show_v()


if __name__ == "__main__":
    main()
